The sequence an is given with the formula: an = n2
mod 12345 + n3 mod 23456.
You need to answer the next queries a lot
of times:
·
find the difference between the maximum and the minimum element among the
values ai, ai + 1, ..., aj;
·
assign to the element ai
the value of j.
Input. The first line contains the number of
queries k (k ≤ 100 000). Each of the next k lines contains one query. The i-th
query contains the numbers xi,
yi.
If xi > 0, find the
difference between the maximum and the minimum element among the values of axi...ayi. It is known that 1 ≤ xi ≤ yi
≤ 100 000.
If xi < 0, assign to the
element a-xi the value of yi. It is known that -100 000
≤ xi ≤ -1 and
|yi| ≤ 100 000.
Output. For each query of the first type print in a separate
line the difference between the maximum and the minimum element on a given
segment.
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
Sample output
34
68
250
234
1
data structures – segment tree
Поскольку в задаче присутствует
модификация элементов, то ее можно рассматривать как задачу динамического RMQ и
следует решать при помощи дерева отрезков. Для этого необходимо реализовать
следующие функции:
·
создание дерева отрезков по массиву а;
·
нахождение минимума и максимума на отрезке;
·
единичную модификацию элемента.
Реализовать дерево отрезков можно
как при помощи дерева, так и линейного массива.
Example
Положим a0 = 0.
Сгенерируем первые 10 элементов последовательности ai:
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
ai |
0 |
2 |
12 |
36 |
80 |
150 |
252 |
392 |
576 |
810 |
1100 |
Выполним запросы, приведенные в
примере:
|
1 3 |
max[1..3] – min[1..3] = 36 – 2 = 34 |
|
2 4 |
max[2..4] – min[2..4] = 80 – 12 = 68 |
|
-2 -100 |
a2 = -100 |
|
1 5 |
max[1..5] – min[1..5] = 150 – (-100) = 250 |
|
8 9 |
max[8..9] – min[8..9] = 810 – 576 = 234 |
|
-3 -101 |
a3 = -101 |
|
2 3 |
max[2..3] – min[2..3] = -100 – (-101) = 1 |
Algorithm
realization
Дерево отрезков храним в векторе SegmentTree длины 4*MAX, где MAX –
максимальное количество элементов, которое может храниться в отрезке. Структура
node хранит
минимальное min и максимальное max значение на отрезке.
#define MAX 100000
struct node
{
int min, max;
} SegmentTree[4*MAX];
На вход процедуре build
построения дерева отрезков передается массив a, номер текущей вершины дерева Vertex и границы отрезка Left и Right, соответствующие вершине Vertex.
void BuildTree(int
*a, int Vertex, int
Left, int Right)
{
if (Left ==
Right)
SegmentTree[Vertex].min =
SegmentTree[Vertex].max = a[Left];
else
{
int Middle
= (Left + Right) / 2;
BuildTree(a, 2*Vertex, Left, Middle);
BuildTree(a, 2*Vertex+1, Middle+1, Right);
Пересчитываем минимальное и максимальное значение на
отрезке [Left,
Right], используя информацию сыновей вершины Vertex.
SegmentTree[Vertex].min =
min(SegmentTree[2*Vertex].min,SegmentTree[2*Vertex+1].min);
SegmentTree[Vertex].max =
max(SegmentTree[2*Vertex].max,SegmentTree[2*Vertex+1].max);
}
}
Вершине Vertex
соответствует отрезок [LeftPos; RightPos]. Функция GetMin возвращает
минимум на отрезке [Left; Right].
int GetMin(int
Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left >
Right) return INF;
if ((Left ==
LeftPos) && (Right == RightPos))
return
SegmentTree[Vertex].min;
int Middle =
(LeftPos + RightPos) / 2;
return
min(GetMin(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)),
GetMin(2*Vertex+1, Middle+1,
RightPos, max(Left,Middle+1),Right));
}
Вершине Vertex соответствует отрезок [LeftPos; RightPos]. Функция GetMax возвращает максимум на отрезке [Left; Right].
int GetMax(int
Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left >
Right) return -INF;
if ((Left ==
LeftPos) && (Right == RightPos))
return
SegmentTree[Vertex].max;
int Middle =
(LeftPos + RightPos) / 2;
return
max(GetMax(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)),
GetMax(2*Vertex+1, Middle+1,
RightPos, max(Left,Middle+1),Right));
}
Вершине Vertex соответствует отрезок [LeftPos; RightPos]. Функция Update присваивает элементу с индексом Position значение NewValue.
void Update(int
Vertex, int LeftPos, int
RightPos,
int
Position, int NewValue)
{
Если вершине Vertex соответствует отрезок,
состоящий из одного элемента (LeftPos
равно RightPos), то мы дошли до листа
дерева отрезков. Минимум и максимум на отрезке, состоящего из одного элемента,
равен NewValue.
if (LeftPos == RightPos)
SegmentTree[Vertex].min =
SegmentTree[Vertex].max = NewValue;
else
{
Иначе вычисляем, в каком – левом или правом сыне вершины Vertex
лежит элемент с индексом Position.
Запускаем рекурсивно его модификацию.
int Middle
= (LeftPos + RightPos) / 2;
if
(Position <= Middle)
Update (2*Vertex, LeftPos, Middle,
Position, NewValue);
else
Update (2*Vertex+1, Middle+1, RightPos,
Position, NewValue);
Пересчитываем значение минимума min и максимума max
в текущей вершине Vertex дерева отрезков.
SegmentTree[Vertex].min =
min(SegmentTree[2*Vertex].min,SegmentTree[2*Vertex+1].min);
SegmentTree[Vertex].max =
max(SegmentTree[2*Vertex].max,SegmentTree[2*Vertex+1].max);
}
}
Основная часть программы. Генерируем последовательность ai согласно приведенной в
условии задаче формуле. Последовательность храним в массиве int a[MAX+1];
for(i = 0; i
<= MAX; i++)
a[i] = (i * i) % 12345 + ((i * i) % 23456 *
i) % 23456;
Строим дерево отрезков.
BuildTree(a,1,0,MAX);
Читаем входные данные и отвечаем на запросы.
scanf("%d",&k);
while(k--)
{
scanf("%d
%d",&x,&y);
if (x > 0)
printf("%d\n",GetMax(1,0,MAX,x,y) -
GetMin(1,0,MAX,x,y));
else
Update(1,0,MAX,-x,y);
}